/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 */

// @lc code=start
class Solution
{
public:
  vector<vector<string>> ans;
  int n;

  vector<vector<string>> partition(string s)
  {
    this->n = s.size();
    vector<string> tmp;
    Backtracking(s, 0, tmp);
    return ans;
  }

  void Backtracking(string& s, int pos, vector<string>& tmp)
  {
    if (pos == n)
      ans.push_back(tmp);
    else {
      for (int i = 1; i + pos <= n; ++i) {
        string sub = s.substr(pos, i);
        if (IsPalindrome(sub)) {
          tmp.push_back(sub);
          Backtracking(s, pos + i, tmp);
          tmp.pop_back();
        }
      }
    }
  }

  bool IsPalindrome(string& s)
  {
    int L = 0, R = s.size() - 1;
    for (; L < R; ++L, --R) {
      if (s[L] != s[R])
        return false;
    }
    return true;
  }
};
// @lc code=end
